The invention relates generally to error correction systems and, more particularly, to systems that use hardware that both encodes the data and produces associated error syndromes.
Encoders for encoding data in accordance with a Reed-Solomon error correction code (xe2x80x9cECCxe2x80x9d) to produce ECC symbols are well known. A conventional encoder that produces xe2x80x9cRxe2x80x9d ECC symbols includes R Galois Field multipliers. The Galois Field multipliers are associated, respectively, with the j roots of the code generator polynomial, g(x). The encoder also includes feedback adders that combine the products associated with a given data symbol with the results of the encoding of the previous data symbol, and j registers that hold the sums produced by the adders. At the end of the encoding, the j registers contain the ECC symbols.
When a data symbol is supplied to the encoder the symbol is combined with the contents of a last register and the result is supplied to the Galois Field multipliers, which simultaneously multiply the results by the roots of g(x). The product produced by a first Galois Field multiplier updates the first register. The products produced by the remaining Galois Field multipliers are combined, respectively, with the contents of the remaining registers and the results are used to update these registers. The last register is thus updated with the sum of (i) the product produced by the last Galois Field multiplier and (ii) the contents of the preceding register. The updated contents of the last register are then combined with the next data symbol, and the result is fed back to the Galois Field multipliers. The remaining feedback adders add the products produced by the multipliers to the results of the encoding of the previous data symbol and supply the sums to update the registers, and so forth. As soon as the last data symbol is encoded, the ECC symbols are read from or clocked out of the R registers and concatenated with the data symbols to produce a data codeword that is transmitted or stored, as appropriate. With such an encoder the latency is the time associated with a single feedback adder, since the adders operate in parallel to produce the updated sums for the registers. Accordingly, the latency is essentially non-existent.
As part of a decoding operation a decoding system manipulates the data symbols of a data code word to produce error syndromes that are then used to locate errors in the data. A conventional error syndrome generator includes R sets of associated update adders, Galois Field multipliers and registers, with each set operating simultaneously and essentially separately to produce the associated error syndrome. Each update adder adds the product produced by the associated Galois Field multiplier to the next data symbol, and updates the associated register with the sum. Each Galois Field multiplier then multiplies the contents of the register by a root of an error syndrome generator polynomial that is associated with the ECC and supplies the product to the associated update adder. The update adder adds the product to the next data symbol, and supplies the sum to the associated register, and so forth. After the last data symbol is supplied to the syndrome generator and added to the products produced by the respective Galois Field multipliers to update the registers, the R registers contain the R error syndromes.
The Galois Field multipliers that are included in the encoder and the syndrome generator are relatively complex components. An article by Gerhard Fettweis and Martin Hassner, A Combined Reed-Solomon Encoder And Syndrome Generator With Small Hardware Complexity, published by IEEE in 1992 describes hardware that uses the same Galois Field multipliers for both the encoding and the syndrome generation. The combined hardware thus uses one-half the number of multipliers that are required for separate encoder and syndrome generator hardware. The article is incorporated herein by reference.
The combined hardware described in the article is depicted in FIG. 1. The hardware includes R sets of associated registers 10, Galois Field multipliers 12, update adders 14 and feedback adders 16. The R registers 10 hold updated sums produced by the R associated update adders 14. Each Galois Field multiplier 12 multiplies the contents of the associated register 10 by a root of the generator polynomial and supplies the product to the associated feedback adder 16. During encoding operations, an associated AND gate 18 passes to the adder 16 the sum produced by the previous feedback adder 16. The adder 16 then adds the propagating sum to the product and passes the result both to the associated update adder 14 and through a next AND gate 18 to the next feedback adder 16. The next feedback adder 16 adds the propagating sum to the product produced by the associated multiplier 12, and the result is supplied to the associated update adder 14 and through the next AND gate 18 to a next feedback adder, and so forth. The feedback adders 16 and associated AND gates 18 thus form a feedback path in which the adders 16 operate as a chain. During syndrome generation operations, the AND gates 18 essentially break the chain of adders by blocking the propagation of a sum from one feedback adder 16 to the next, and the R sets of associated registers 10, multipliers 12 and adders 14 operate separately to produce the R error syndromes.
With the combined hardware there is a latency in the encoding operations that corresponds to the time it takes the propagating sum to pass through the chain of R feedback adders as each symbol is encoded. If the chain of adders is long, it restricts the speed with which the data is encoded by setting a minimum time for a clock cycle, that is, a minimum time for the encoding of each symbol, since in each clock cycle the corresponding propagating sum must pass through the entire chain of R adders.
The invention is a parallel input/output combined encoding and syndrome generating system that encodes two symbols per clock cycle, and thereafter, produces two redundancy symbols per clock cycle. The system thus produces the R redundancy symbols and the R error syndromes in one-half the time of the conventional Fettweis-Hassner hardware.
More specifically, for an n-symbol code word with 2k information symbols cnxe2x88x921, to cnxe2x88x922k, the symbols cnxe2x88x921, cnxe2x88x923, cnxe2x88x925 . . . are supplied, in turn, to a first input line while the symbols cnxe2x88x922, cnxe2x88x924, cnxe2x88x926, . . . are supplied, in turn, to a second input line. In a first clock cycle, the symbol cnxe2x88x921 is combined with the contents of the R registers and multiplied by the roots of the generator polynomial. The respective products then are combined with the paired symbol cnxe2x88x922 and the resulting sums are multiplied also by the roots of the generator polynomial. These products are then summed in the chain of R adders and the registers are appropriately updated with the results of the encoding of the pair of symbols. Accordingly, a sum is propagated along the chain of R adders once to encode the two symbols.
During the next clock cycle, the next pair of information symbols are encoded, with cnxe2x88x923 supplied to the first input line and cnxe2x88x924 supplied to the second input line, and so forth. During the kth clock cycle, when the last of the pairs of information symbols are being encoded, the system produces the first two redundancy symbols. More specifically, the first redundancy symbol is the kth update value for the last register rRxe2x88x921, which is produced by the chain of R adders. The system then manipulates the update value, as discussed in more detail below, to produce the second redundancy symbol in the same clock cycle. During the k+1st clock cycle, the pair of redundancy symbols are fed back to the two input lines and encoded, as discussed above, to produce the next pair of redundancy symbols, and so forth. The system thus produces the R redundancy symbols in                     2        ⁢        k            +      R        2    =      n    2  
clock cycles.
For decoding, the chain of R feedback adders is broken, and each set of adders and multipliers operates separately to update the associated register with the results of the encoding of pairs of code word symbols. The system thus produces the R error syndromes in   n  2
clock cycles.
The gate-count of the parallel input/output system may be reduced, essentially by further manipulating the propagating sum, as discussed in more detail below.